class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}
// 快慢指针 + 链表反转
function isPalindrome(head: ListNode | null): boolean {
    if (!head || !head.next) return true;

    // 步骤1：找到链表中点
    let slow: ListNode | null = head;
    let fast: ListNode | null = head;

    while (fast && fast.next) {
        slow = slow!.next;//每次走一步
        fast = fast.next.next;//每次走两步，走到最后时，slow刚好在中点处
    }

    // 步骤2：反转后半部分链表
    let secondHalf = reverseList(slow);
    let firstHalf: ListNode | null = head;

    // 步骤3：比较前后两部分
    let result = true;
    let tempSecondHalf = secondHalf; // 保存用于恢复链表

    while (secondHalf) {
        if (firstHalf!.val !== secondHalf.val) {
            result = false;
            break;
        }
        firstHalf = firstHalf!.next;
        secondHalf = secondHalf.next;
    }

    // 步骤4：恢复链表（可选）
    reverseList(tempSecondHalf);

    return result;
}

// 辅助函数：反转链表
function reverseList(head: ListNode | null): ListNode | null {
    let prev: ListNode | null = null;
    let current: ListNode | null = head;

    while (current) {
        const nextTemp = current.next;
        current.next = prev;
        prev = current;
        current = nextTemp;
    }

    return prev;
}